1. Field of the Invention
The present invention relates to a progressive coding/decoding method and apparatus of three-dimensional (3D) mesh data, characterized by error resilience and incremental build-up, used in the fields of motion picture experts group-4 synthetic and natural hybrid coding (MPEG-4 SNHC), virtual reality modelling language (VRML) and the like.
2. Description of the Related Art
In transmitting 3D objects composed of 3D mesh data, it is very important to incrementally and error-resiliently restore transmitted data as well as to effectively code the 3D mesh data. In the event that a data error is generated due to a transmission path error, progressive restoration allows transmitted data to be partially restored and minimizes the amount of mesh data to be retransmitted. Error-resilient restoration allows transmitted data to be independently restored in units of the transmitted data, irrespective of presence of errors generated in a specific unit of the transmitted data, thereby enhancing-the data restoration efficiency and reducing the standby time of a user. The progressive and error-resilient restoration method which is robust against such communication path errors can be effectively used in wireless communications or low transmission rate communications. The purposes of the present invention are to construct connectivity, geometry and photometry necessary for progressively coding 3D mesh data and providing resilience against data errors, and to propose a coding/decoding method of the same.
In the conventional coding method of 3D mesh data, since the mesh data is wholly coded, it is almost impossible to partially restore data before an entire bitstream is received. Also, due to transmission path errors generated during transmission, even if only a part of the data is damaged, the entire bitstream of data must be received again. For example, ISO/IEC JTC1/SC29/WG11 MPEG98/W2301, xe2x80x9cMPEG-4 SNHC Verification Model 9.0xe2x80x9d proposed by I.B.M. Corp. is currently being adopted as an MPEG-4 SNHC 3D mesh coding technology.
In MPEG-4 SNHC, mesh coding is designed based on VRML. In the VRML, a mesh is described in a node form referred to as an IndexedFaceSet. One of the main technologies for coding mesh data is a topological surgery proposed by I.B.M. Corp. According to this technology, it is assumed that a given mesh is the same as a sphere topologically. Then, the mesh is cut along a given cutting-edge to generate a triangle spanning graph having a binary tree structure. Here, the cutting-edge defined for cutting the mesh is configured such that it connects vertices, that is, it is given as a tree structure having a loop. The cutting-edge is referred to as a vertex spanning graph. Thus, two tree structures, that is, the triangle spanning graph and the vertex spanning graph, are coded/decoded, thereby restoring the original mesh without loss.
According to MPEG-4 SNHC, although there may be multiple IndexedFaceSets in a VRML file, compression is basically performed on the unit of one IndexedFaceSet. However, it is allowed to form a single IndexedFaceSet by several connected components.
In general, for fast graphics processing, modeling must be performed in units of triangles. These triangles are not formed randomly but are preferably connected to each other in the form of strips or fans. Also, the more symbols that are repeatedly represented, the better the compressibility is. To this end, a mesh formed by a single long triangular strip is proposed by I.B.M. Corp. in view of fast graphics processing and better compressibility.
FIGS. 1A through 1F illustrate a conventional procedure for generating a vertex spanning graph and a triangle spanning graph in an example of a triangular mesh. FIGS. 1A and 1D illustrate a method for cutting a mesh along cutting-edges drawn by a thick line. FIG. 1B illustrates the overall form of the cutting-edges. FIG. 1E illustrates the configuration of edges and vertices produced by cutting along the cutting-edges shown in FIG. 1B. FIG. 1C illustrates a vertex spanning graph made by connecting vertices which reference cutting points. FIG. 1F illustrates a triangle spanning graph defined as a strip which is a set of connected triangles generated by cutting the mesh along the vertex spanning graph. Also, if the triangle spanning graph is generated by the method shown in FIGS. 1A through 1F, the length of one of two branching runs in the triangle spanning graph can be considerably shorter than the other.
FIGS. 2A through 2D illustrate an example of a topological surgery technique applied to actual mesh data. In a vertex spanning graph, a branch can branch off into several branches. FIG. 3 illustrates an example of a vertex spanning graph having a loop, in which a vertex run returns to a location of one of the previous vertices. Since a mesh is generally formed of several connected components, each connected component forming the mesh generates a pair of a vertex spanning graph shown in FIG. 1F and a triangle spanning graph shown in FIG. 1C. Therefore, if a single IndexedFaceSet is coded, several triangle spanning graph-vertex spanning graph pairs can be obtained.
The method for restoring the data coded by the above-described topological surgery technology is as follows:
1. A bounding loop is generated using a vertex spanning graph.
2. When the third vertex of a triangle branching off in a triangle spanning tree is referred to as a Y-vertex, the Y-vertex is calculated using bitstreams of the triangle spanning tree, and sets of triangles or polygons having connectivity of a strip shape are generated. Here, the triangles or polygons are formed using a triangle marching bit of the triangle spanning graph.
3. Meshes are restored in accordance with the topological geometry using the mesh data of a tree structure constructed through the steps 1 and 2.
Lossless compression using arithmetic coding of the vertex spanning graph and the triangle spanning graph has been proposed by I.B.M. Corp. However, according to this method, in order to reconstruct the original structure, all bitstreams must be input and the following problems arise:
1. Since all bitstreams must be input in order to decode mesh data, in any event of a transmission error, all bitstreams must be retransmitted.
2. In the case where the magnitude of compressed data is large, compared to the bandwidth, it takes a long period of time to transmit the data completely and a user must wait during such a period of time. In order to reduce the user""s waiting time, meshes must be partially restored and rendered using the transmitted data. However, according to the existing technologies, the number of triangles which can be restored is small, compared to the amount of transmitted bits, in view of the structure of bitstreams.
To overcome the disadvantages of the conventional technology, the following functions must be satisfied.
1. Mesh data must be partitioned by an effective unit size in view of the bandwidth of a transmission path or the characteristic of a decoder, and error resilience must be allowed so that bitstreams having the unit size are restored and rendered by the decoder.
2. Incremental coding/decoding methods must be allowed so that partial restoration and rendering of only a part of the currently received data is possible.
Implementation of these two functions while maintaining the basic structure of the conventional method proposed by I.B.M. Corp. depends on effective processing of the bounding loop and Y-vertex, as shown in FIG. 4. In FIG. 1F, points 10, 14 and 18 are Y-vertices. In order to calculate a Y-vertex, at least one of two branching triangle runs must be processed. In other words, for triangles within a triangle run, the indices of the three vertices of each triangle can be determined using the marching bit pattern and the bounding loop. However, in order to determine the indices of Y-vertices which are the third vertices of branching triangles, all bitstreams for one of two triangle runs next to the branching triangles must be received. Therefore, the triangles next to the branching triangles cannot be restored to be rendered until subsequent bitstreams are received. This problem does not occur in the conventional method proposed by I.B.M. Corp., which is based on the assumption that all bitstreams are received in the decoder. However, in order to restore and display the triangles incrementally, this problem must be solved.
The definitions of terms used in the art related to the invention will be first described as follows.
Polygonal mesh: A polygonal mesh is defined by coordinates (geometry) in a 3D space of vertices, the relationship (connectivity) between the respective faces and the vertices forming the faces, and photometry such as color, normal or texture information, which do not affect the geometric structure of a mesh but affect the appearance of the mesh.
Face: A face is a set of vertex indices and a corner is a pair of (face, vertex) sets. A simple face is a set of vertex indices in which different indices form a face. In this invention, only a polygonal mesh consisting of simple faces will be dealt with.
Edge: A edge is a pair of vertex indices. If an edge appears on only one face in a polygonal mesh, the edge is defined as a xe2x80x9cboundaryxe2x80x9d edge. If one and the same edge appears on several faces, the edge is defined as a xe2x80x9csingularxe2x80x9d edge. If an edge appears on only two neighboring faces, the edge is defined as an xe2x80x9cinternalxe2x80x9d edge. The boundary edge and the internal edge are defined as xe2x80x9cregularxe2x80x9d.
Dual graph: One point is defined within each face of a mesh and then points defined above and passing through the internal edge between neighboring faces are connected to be defined as a dual graph. FIG. 5A illustrates a polygonal mesh and FIG. 5B is a dual graph of the polygonal mesh shown in FIG. 5A.
Virtual reality modeling language (VRML): The VRML is a graphic standard format prepared for describing and transmitting a virtual space over the Internet.
Moving Picture Experts Group (MPEG): The MPEG is a group for carrying out international standardization activities for standardizing compression formats for transmitting a variety of media such as video.
Mesh: A mesh is a representation of an object constructed of several polygons.
Node: A node is a vertex in a vertex spanning graph or a minimum description unit used in VRML.
Topological surgery: Topological surgery is a mesh coding method proposed by I.B.M. Corp. in which a mesh is cut along a given path in order to make the mesh into the form of strips.
Vertex spanning graph: A vertex spanning graph is a path for cutting a mesh in the topological surgery.
Triangle spanning graph: A triangle spanning tree is a binary tree in the form of a triangle strip produced by cutting a mesh along the vertex spanning graph.
vlast: vlast indicates whether the current run is the last branch or not. If the current run is the last branch, the value of vlast is 1; otherwise it is 0.
vleaf: vleaf indicates whether the current vertex run ends with a leaf or a branch. If the current vertex run ends with a leaf, the value of vleaf is 1; otherwise it is 0.
vrun: A vrun is a set of connected vertices and ends with a branch or vleaf.
vlength is the length of a vertex run.
loopstart: The leaf of a vertex run may meet another vertex run to form a loop. In such a case, the start of the loop is indicated by the loopstart.
loopend: In the case when the leaf of a vertex run forms a loop, the end of the loop is indicated by the loopend.
loopmap: A loopmap indicates connectivity between the loopstart and the loopend and is a set of indices connecting edges from the loopend to the loopstart.
trun: A trun is a set of consecutive triangles and the end thereof is a leaf triangle or a branching triangle.
tleaf: tleaf indicates whether the run of a triangle ends with a leaf triangle or a branching triangle. If the run of a triangle ends with a leaf triangle, the value of tleaf is 1; otherwise it is 0.
tmarching: tmarching describes the marching aspect of triangles. If a strip has an edge at its right boundary, the value of tmarching is 1. If a strip has an edge at its left boundary, the value of tmarching is 0.
polygonedge: polygonedge indicates whether a current edge is given from the original mesh model or inserted for representing the polygon as a set of triangles. If a current edge is given from the original mesh model, the value of polygonedge is 1; otherwise it is 0.
triangulated: triangulated indicates the presence of a polygon in the mesh.
nvertices: nvertices indicates the number of vertices.
nloops: nloops indicates the number of loops.
nvedges: nvedges indicates the magnitude of a vrun.
nvleaves: nvleaves indicates the number of leaves in a vertex spanning graph.
bitspernvedges: bitspernvedges indicates the number of bits used for nvedges.
simple: If loops are present in a vertex spanning graph, the value of simple is 0, and 1, otherwise.
ntriangles: ntriangles indicates the number of triangles in a triangle spanning graph.
ntbranches: ntbranches indicates the number of triangles branching off in a triangle spanning graph.
nmarchingtrans and nmarchingkeepleft are statistical models for compression of Tmarching.
npolytrans and nkeeppoly are statistical models for compression of Polygonedge.
FIG. 6 is a conceptual block diagram of a conventional three-dimensional (3D) mesh information coding method. In FIG. 6, a 3D mesh object 100 is divided into connectivity, geometry and photometry and coded by a coding part 101 including a connectivity coder 102, a geometry coder 103 and a photometry coder 112. Here, vertex structure information 105 is transmitted from the connectivity coder 102 to the geometry coder 103. The information compressed by the connectivity coder 102, the geometry coder 103 and the photometry coder 112 is combined into a bitstream and the bitstream is compressed to a compressed bitstream 111 by an entropy coder 104.
The compressed bitstream 111 is input to a decoding part 112. In other words, the compressed bitstream 111 is decompressed and divided into connectivity, geometry and photometry via an entropy decoder 106 to then be decoded by a connectivity decoder 107, a geometry decoder 108 and a photometry decoder 113, respectively. Like in the coding part 101, vertex structure information 109 is transmitted from the connectivity decoder 107 to the geometry decoder 108. A decoded 3D mesh object 110 can be constructed using the decoded connectivity, geometry and photometry.
In FIG. 6, a 3D mesh can be transmitted in the form of a compressed bitstream in a communication path. However, since the conventional MPEG data compression method employs the entropy coder 104, the method is weak against transmission errors generated in a communication path. Therefore, the present invention proposes a technology for solving the transmission errors and progressively restoring 3D mesh data using transmitted connectivity, geometry and other information.
To solve the above problems, it is an objective of the present invention to provide a method for progressively coding/decoding 3D mesh information, by which a network load and a transmission time can be reduced by re-transmitting only a part where a transmission error is generated or restoring the data independently from the part having a transmission error, an increase in the amount of bits generated due to error restoration dependent on network layers can be minimized, and the 3D mesh information can be progressively restored using connectivity, geometry and photometry of the transmitted part.
Accordingly, to achieve the above objective, there is provided a method of coding a polygonal three dimensional (3D) mesh object (MO) comprising the steps of (a) dividing the polygonal 3D MO into one or more connected components, (b) generating a vertex graph and triangle tree/triangle data for each of the connected components, and (c) reconstructing the vertex graph and triangle tree/triangle data constituting the connected component in conformity with mesh object base layers (MOBLs) each capable of being independently decoded for the respective connected components and then coding the same.
According to another aspect of the present invention, there is provided a progressive and error-resilient method of coding a polygonal three dimensional (3D) mesh object (MO), including the steps (a) dividing the polygonal 3D MO into one or more connected components, (b) generating a vertex graph and a pair of triangle tree/triangle data for each of the connected components, and (c) coding the vertex graph and triangle tree/triangle data constituting the connected components in conformity with mesh object base layers (MOBLs) each having a fixed type of bitstream capable of being independently decoded for the respective connected components.
According to the present invention, there is also provided a progressive and error-resilient coding method of a polygonal three dimensional (3D) mesh object (MO), including the steps (a) dividing the polygonal 3D MO into one or more connected components, (b) generating a vertex graph and a pair of triangle tree/triangle data for each of the connected components, and (c) coding the vertex graph and triangle tree/triangle data constituting the connected components in conformity with mesh object base layers (MOBLs) each having a variable bitstream type in accordance with the properties of information to be coded, capable of being independently decoded for the respective connected components.
According to another aspect of the present invention, there is provided a progressive and error-resilient coding method of a polygonal three dimensional (3D) mesh object (MO), including the steps (a) dividing the polygonal 3D MO into one or more connected components, (b) generating a vertex graph and a pair of triangle tree/triangle data for each of the connected components, and (c) coding the vertex graph constituting the connected components, and (d) constructing the triangle tree/triangle data as virtual connected components and coding the same by adding virtual bit pairs to data partitions obtained by partitioning the triangle tree/triangle data.
To achieve the above object of the present invention, in coding a triangle three dimensional (3D) mesh object (MO) for incremental build-up and error resilience, there is provided a method for partitioning the triangle 3D MO into data partitions to be packetized, the method including the steps (a) calculating total bit generation amounts of triangles while the triangles contained in a triangle tree are sequentially traversed, (b) accumulating the total bit generation amounts calculated in step (a), and c) if the accumulated value of step (b) is smaller than the product of a packet size and a packet allowance, repeatedly performing the steps (a) and (b) on the next traversed triangle contained in the triangle tree, and if not, triangle tree/triangle data of the traversed triangles are partitioned into data partitions to be packetized.
The present invention also provides a progressive and error-resilient decoding method of a polygonal three dimensional (3D) mesh object (MO), including the steps (a) dividing input bitstreams into units of mesh object base layers (MOBLs), (b) determining a partition type of the MOBLs, (c) if a vertex graph is contained in the MOBLs, decoding the vertex graph to generate a bounding loop table, (d) if triangle tree/triangle data is contained in the MOBLs, decoding the triangle tree/triangle data to generate 3D MO, and (e) repeatedly performing the steps (a) through (d) to generate a 3D MO.
According to another aspect of the present invention, there is provided a progressive and error-resilient decoding method of a polygonal three dimensional (3D) mesh object (MO), including the steps (a) dividing input bitstreams into units of mesh object base layers (MOBLs), (b) determining a partition type of the MOBLs, (c) if a vertex graph is contained in the MOBLs, decoding the vertex graph to generate a bounding loop table, (d) if triangle tree/triangle data is contained in the MOBLs, decoding the triangle tree/triangle data in units of connected components to generate triangle 3D MO, and (e) if the connected components in the step (d) are virtual connected components, repeatedly performing the steps (a) through (d), and if not, completing the generation of a triangle 3D MO.